package java学习.leetcode.editor.cn;

import java学习.算法.链表.Linkedlist;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author 刘世锦
 * 2022-12-25 16:47:36	 当前时间
 */
//给定二叉搜索树（BST）的根节点 root 和一个整数值 val。 
//
// 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：root = [4,2,7,1,3], val = 2
//输出：[2,1,3]
// 
//
// 示例 2: 
//
// 
//输入：root = [4,2,7,1,3], val = 5
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 数中节点数在 [1, 5000] 范围内 
// 1 <= Node.val <= 107 
// root 是二叉搜索树 
// 1 <= val <= 107 
// 
// Related Topics 树 二叉搜索树 二叉树 
// 👍 349 👎 0

public class 二叉搜索树中的搜索{
	public static void main(String[] args) {
		Solution solution = new 二叉搜索树中的搜索().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

	/** 复习  @author 刘世锦
	 *  @date  2023/2/7 11:11
	 */
	public TreeNode searchBST(TreeNode root, int val) {
		if (root==null){
			return null;
		}
		if (root.val==val){
			return root;
		}
		if (root.val>val){
			return searchBST(root.left,val);
		}else {
			return searchBST(root.right,val);
		}


	}




	// 复习end

	public TreeNode searchBSTBFS1(TreeNode root, int val) {
		if(root==null){
			return null;
		}
		if(root.val == val){
			return root;
		}
		TreeNode left = searchBST(root.left, val);
		TreeNode right = searchBST(root.right, val);
		if (left!=null){
			return left;
		}else{
			return right;
		}
	}
    public TreeNode searchBSTBFS(TreeNode root, int val) {
		if(root==null){
			return null;
		}
		if (root.val == val){
			return root;
		}
		if (root.val>val){
			return searchBSTBFS(root.left,val);
		}else{
			return searchBSTBFS(root.right,val);
		}
    }

	public TreeNode searchBST1(TreeNode root, int val) {
    	if (root==null){
    		return null;
		}
    	while (root!=null){
			if (root.val==val){
				return root;
			}
			if (root.val>val){
				root = root.left;
			}else if (root.val<val){
				root = root.right;
			}
		}
    	return null;
	}


		/**
         *
         * _   1 3 _
         *
         */
	public TreeNode searchBSTDFSQueue(TreeNode root, int val) {
		Queue<TreeNode> queue = new LinkedList<>();
		if (root!=null){
			queue.offer(root);
			while (!queue.isEmpty()){
				TreeNode node = queue.poll();
				if (node.val==val){
					return node;
				}
				if (node.left!=null){
					queue.offer(node.left);
				}
				if (node.right!=null){
					queue.offer(node.right);
				}
			}
		}
		return null;
	}
	public TreeNode searchBSTStack(TreeNode root, int val) {
		Stack<TreeNode> stack = new Stack<>();
		if (root!=null){
			stack.push(root);
			while (!stack.isEmpty()){
				TreeNode node = stack.pop();
				if (node.val==val){
					return node;
				}
				if (node.right!=null){
					stack.push(node.right);
				}
				if (node.left!=null){
					stack.push(node.left);
				}
			}
		}
		return null;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
